package sort;

public class MergeSort {
	long[] emptyList = new long[0];
	long[] oneElementList = new long[1];
	/**
	 * mergesort algorithm
	 */
	public MergeSort() {
	}
	/**
	 * 
	 * @param incList sorted incList
	 * @return  sorted incList
	 */
	public long[] mergeSort( long[] incList ) {
		if(incList.length == 0){return emptyList;}
		if(incList.length == 1){oneElementList[0]=1;return oneElementList;}
		long[] tempList = new long[incList.length];
		return mergeSort( incList, tempList, 0, incList.length - 1 );
	}
	/**
	 * Convenience function
	 * @param incList list to sort
	 * @param tempList temporary list
	 * @param left most left item
	 * @param right most right item
	 * @return sorted incList
	 */
	private long[] mergeSort( long[] incList, long[] tempList, int left,
			int right ) {
		if( left < right ){
			int center = ( left + right ) / 2;
			mergeSort( incList, tempList, left, center );
			mergeSort( incList, tempList, center + 1, right );
			return merge(incList, tempList, center + 1, left, right);
		}
		return null;
	}
	/**
	 * merge everything to a list
	 * @param incList list to sort
	 * @param tempList temporary list
	 * @param center the index for the middle item
	 * @param left most left item
	 * @param right most right item
	 * @return sorted incList
	 */
	private long[] merge(long[] incList, long[] tempList, int center, int left, int right) {
		int leftEnd = center - 1; //most right position on the left side
		int elements = right - left + 1; //all elements in list
		int temp = left; //most left position
		
		while( left <= leftEnd && center <= right ){
			if( incList[left] - incList[center] <= 0 ){
				tempList[ temp++ ] = incList[ left++ ];
			} else {
				tempList[ temp++ ] = incList[ center++ ];
			}
		}
		while( left <= leftEnd ){
			tempList[ temp++ ] = incList[ left++ ];
		}
		while(center <= right){
			tempList[ temp++ ] = incList[ center++ ];
		}
		//make one list
		for( int i = 0; i < elements; i++, right--){
			incList[ right ] = tempList[ right ];
		}
		return incList;
	}
	/**
	 * print the list
	 * @param incList list that will be printed
	 */
	public void printList(long[] incList){
		int listElements = incList.length;
		System.out.println("\nmergesort \n");
		for(int i = 0; i < listElements; i++){
			System.out.print(incList[i] + ", ");
		}
	}
}
